4. Median of Two Sorted Arrays

Posted on | In

4. Median of Two Sorted Arrays

description:

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

解答

中位数是整个序列从小到大排列，位置处于最终间的数。

本道题是求两个已经排好序的数组的中位数

假设一个数组为A，另一个数组为B

那么中位数把数组A，B的左边和右边分为两块，让左边的大小和右边的大小相等。

如下图所示。

左边 右边
A[0], A[1], …, A[i-1] A[i], A[i+1], …, A[m-1]
B[0], B[1], …, B[j-1] B[j], B[j+1], …, B[n-1]

其中A[i-1] 小于 A[i]（已知），B[j-1] 小于 B[j]（已知）， A[i-1]小于B[j]，B[j-1]小于A[i]

假设数组A的长度为m，数组B的长度为n ,m的左边有i个，n的左边有j个，则i + j = m - i + n - j + 1，所以j = $\frac{m + n + 1}{2} - i$

为了保证j > 0，我们需要保证$\frac{m + n + 1}{2} - i$，所以我们需要保证m小于n。

所以本算法的精髓就是通过对i进行二分查找来找到一个i，满足 A[i-1] 小于 B[j] ，B[j-1] 小于 A[i] 时，即可以把两个数组划分为等长的两部分，即可以找到中位数。

当找到的i使得 A[i - 1] > B[j] 时，说明i过大，我们应该在i的左边进行二分查找。

当找到的i使得A[i] < B[j - 1] 时，说明i过小，我们应该在i的右边进行二分查找。

这里需要注意，当i等于0的时候 A[i - 1] 不存在，当 i = m 时 A[i] 不存在，j也是如此，所以我们需要对这些边界条件进行特殊处理。

最后根据m + n的奇偶性进行返回，当m + n为奇数时，返回左边的最大值，当m + n为偶数时，返回$\frac{左边的最大值+右边的最大值}{2}$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    	if (nums1.size() > nums2.size() ) 
    		return findMedianSortedArrays(nums2, nums1);
    	auto m = nums1.size();
    	auto n = nums2.size();
    	int lo = 0, hi = m, halfLen = (m + n + 1) / 2;
    	while (lo <= hi) {
    		auto i = (lo + hi) / 2;
    		auto j = halfLen - i;
    		//当i等于m时，j可能为0，nums2[j - 1]不存在
    		if (i < m && nums1[i] < nums2[j - 1] )
    			lo = i + 1;
    		//当i等于0时，nums1[i - 1]不存在
    		else if (i > 0  && nums1[i - 1] > nums2[j])
    			hi = i - 1;
    		else{

    			int leftMax = 0;
    			int rightMin = 0;
    			//先求左边的最大值，如果m + n为奇数，则左边的最大值就是中位数，直接返回
    			if (i == 0) {
    				leftMax = nums2[j - 1];
    			}
    			else if (j == 0) {
    				leftMax = nums1[i - 1];
    			}
    			else {
    				leftMax = max(nums1[i - 1], nums2[j - 1]);
    			}
    			if ((m + n) % 2 == 1)
    				return leftMax;
    			//求右边的最大值
    			if (i == m) {
    				rightMin = nums2[j];
    			}
    			else if (j == n) {
    				rightMin = nums1[i];
    			}
    			else {
    				rightMin = min(nums2[j], nums1[i]);
    			}
    			return (leftMax + rightMin) / 2.;
    		}
    	}
    	return -1;
    }
};